package com.nav.util;

public class Tree<T extends Comparable<T>> {
	MyNode<T> root;
	private static class MyNode<T extends Comparable<T>> {
		T e;
		MyNode<T> l, r;
		public MyNode(T e) {
			this.e = e;
		}
		public MyNode<T> removeRoot() {
			if(l == null)
				return null;
			if(l.r == null) {
				MyNode<T> lmax = l;
				lmax.l = l.l;
				lmax.r = r;
				return lmax;
			}
			MyNode<T> n = l;
			while(n.r.r != null)
				n = n.r;
			MyNode<T> lmax = n.r;
			lmax.l = l;
			lmax.r = r;
			n.r = n.r.l;
			return lmax;
		}
		public String toString() {
			if(l == null && r == null)
				return e.toString();
			return "{" + e + ", " + l + ", " + r + "}";
		}
	}
	public void add(T e) {
		if(root == null)
			root = new MyNode<T>(e);
		else {
			MyNode<T> n = root;
			while(e.compareTo(n.e) < 0 && n.l != null || e.compareTo(n.e) >= 0 && n.r != null) {
				if(e.compareTo(n.e) < 0)
					n = n.l;
				else
					n = n.r;
			}
			if(e.compareTo(n.e) < 0)
				n.l = new MyNode<T>(e);
			else
				n.r = new MyNode<T>(e);
		}
	}
	public T getMin() {
		if(root == null)
			return null;
		MyNode<T> n = root;
		while(n.l != null)
			n = n.l;
		return n.e;
	}
	public T getMax() {
		if(root == null)
			return null;
		MyNode<T> n = root;
		while(n.r != null)
			n = n.r;
		return n.e;
	}
	public T removeMax() {
		if(root == null)
			return null;
		T e;
		if(root.r == null) {
			e = root.e;
			root = root.l;
		} else {
			MyNode<T> n = root;
			while(n.r.r != null)
				n = n.r;
			e = n.r.e;
			n.r = n.r.l;
		}
		return e;
	}
	public T removeMin() {
		if(root == null)
			return null;
		T e;
		if(root.l == null) {
			e = root.e;
			root = root.r;
		} else {
			MyNode<T> n = root;
			while(n.l.l != null)
				n = n.l;
			e = n.l.e;
			n.l = n.l.r;
		}
		return e;
	}
	public boolean remove(T e) {
		if(root == null)
			return false;
		if(e.compareTo(root.e) == 0) {
			if(root.l == null)
				root = root.r;
			else if(root.r == null)
				root = root.l;
			else
				root = root.removeRoot();
			return true;
		}
		MyNode<T> p = root, c = e.compareTo(p.e) < 0 ? p.l : p.r;
		while(c != null && e.compareTo(c.e) != 0) {
			p = c;
			c = e.compareTo(p.e) < 0 ? p.l : p.r;
		}
		if(c == null)
			return false;
		if(c.l == null) {
			if(p.r == c)
				p.r = c.r;
			else
				p.l = c.r;
		} else if(c.r == null) {
			if(p.r == c)
				p.r = c.l;
			else
				p.l = c.r;
		} else {
			if(p.r == c)
				p.r = c.removeRoot();
			else
				p.l = c.removeRoot();
		}
		return true;
	}
	public String toString() {
		if(root == null)
			return "{}";
		return root.toString();
	}
}
